package algorithm.sort;

import time.Timewait;

/**
 * 插入排序
 * 时间复杂度		最优情况为 O(n)		最坏情况为 O(n^2)
 * 
 * 优化
 * 折半插入排序：该类优化有二分的思想，是在将待排序的元素与有序部分的元素比较时，
 * 				不再挨个比较，而是用二分折中的方式进行比较，加快比较效率
 * 2-路插入排序：该方法是在折半插入排序的基础上再进行改进的算法，
 * 				其目的是减少排序过程中移动记录的次数，付出的代价是n个记录的辅助空间
 * 				假设原数组为arr，另设一个相同类型的数组tempArr，先将arr[0]赋值给tempArr[0]，
 * 				并将tempArr[0]看成是在有序序列中处于中间位置的元素，
 * 				然后从arr[1]起一次插入到tempArr[1]之前或之后的有序序列中。
 * 				先将待插元素和tempArr[0]做比较，若小于tempArr[0]，则插入tempArr[0]之前的有序部分；
 * 				反之，将其插入tempArr[0]之后的有序部分中
 * 
 * 适用场景：待排序序列的元素个数不多(<=50)，且元素基本有序
 * */
public class InsertionSort {
	public static void sort(int[] arr) {
		for(int i = 1; i < arr.length; i++)
			for(int k = i - 1, j = i; k >= 0; k--)
				if(arr[j] < arr[k]) {
					Swap.swap(arr, j, k);
					j = k;
				}
	}
	
	public static void sortOptimize(int[] arr) {		// 折半插入排序
		for(int i = 1; i < arr.length; i++) {
			int left = 0, right = i - 1;
			while(left <= right) {
				int middle = (left + right) / 2;
				if(arr[i] < arr[middle])
					right = middle - 1;
				else
					left = middle + 1;
			}
			int temp = arr[i];
			for(int j =  i - 1; j > right; j--)
				arr[j + 1] = arr[j];
			arr[right + 1] = temp;
		}
	}

	public static void sortOptimize2(int[] arr) {	// 2-路插入排序，存在bug
		int j, first, last, mid, len = arr.length;
		/*临时数组*/
		int[] tempArr = new int[len];
		tempArr[0] = arr[0];
		/*first和last分别指临时数组tempArr中排好序的元素的第一个和最后一个位置*/
		first = last = 0;
		for(int i = 1; i<len; i++){
			/*j 是调整系数*/
			if(first > last){
				j = len - 1;
			}else{
				j = 0;
			}
			/*tempArr中间元素的位置*/
			mid = ((first+last+j)/2)%len;
			/*arr[i]应该插入在tempArr的前半部分*/
			if(arr[i] < tempArr[mid]){
				/*j指向tempArr数组中的第一个元素*/
				j = first;
				/*first 前移，取余是为了实现循环数组效果*/
				first = (first-1+len)%len;
				/*待插元素大于 j 所指元素*/
				while(arr[i] > tempArr[j]){
					/*j 所指元素前移，取余是为了实现循环数组效果*/
					tempArr[(j-1+len)%len] = tempArr[j];
					/*j 指向下一个元素*/
					j = j+1;
				}
				/*移动结束，待插元素插在tempArr[j]前*/
				tempArr[(j-1+len)%len] = arr[i];
				/*arr[i]应该插入在tempArr的后半部分*/
			}else{
				/*j指向tempArr数组中的最后一个元素*/
				j = last;
				/*last后移， 指向插入后的最后一个元素*/
				last++;
				/*待插元素小于 j 所指元素*/
				while(arr[i] < tempArr[j]){
					/*j 所指元素后移*/
					tempArr[(j+1)%len] = tempArr[j];
					/*j 指向上一个元素*/
					j = (j-1+len)%len;
				}
				/*移动结束，待插元素插在tempArr[j]后*/
				tempArr[(j+1)%len] = arr[i];
			}
		}
		/*把在tempArr中排好序的元素依次赋给arr*/
		for(int i = 0; i < len; i++){
			arr[i] = tempArr[(first+i)%len];
		}
	}
	
	public static void main(String[] args) {
		int[] arr = InputSequence.randomIntArray(3900, 10, 1000);
		int[] arr2 = new int[arr.length];
		int[] arr3 = new int[arr.length];
//		System.out.println("原序列：");
		for(int i = 0; i < arr.length; i++) {
//			System.out.print(arr[i] + " ");
			arr2[i] = arr[i];
			arr3[i] = arr[i];
		}
		String time = Timewait.timewait(() -> sort(arr));
		System.out.println("\n插入排序：");
//		for(int i = 0; i < arr.length; i++)
//			System.out.print(arr[i] + " ");
		System.out.println(time);
		time = Timewait.timewait(() -> sortOptimize(arr2));
		System.out.println("\n折半插入排序：");
//		for(int i = 0; i < arr2.length; i++)
//			System.out.print(arr2[i] + " ");
		System.out.println(time);
		time = Timewait.timewait(() -> sortOptimize2(arr3));
		System.out.println("\n2-路插入排序：");
//		for(int i = 0; i < arr3.length; i++)
//			System.out.print(arr3[i] + " ");
		System.out.println(time);
	}
}
